package offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/2/3
 **/
@FunctionalInterface
public interface FindMinFibonacciNumbers {
    /**
     * Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
     *
     * The Fibonacci numbers are defined as:
     *
     * F1 = 1
     * F2 = 1
     * Fn = Fn-1 + Fn-2 for n > 2.
     * It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.
     *
     * @param k
     * @return
     */
    int findMinFibonacciNumbers(int k);
}
class FindMinFibonacciNumbersImpl1 implements FindMinFibonacciNumbers{
    static final int TEST_01 = 513314;
    public static void main(String[] args) {

        for (int i = 1; i <= 30; i++) {
            System.out.println(new FindMinFibonacciNumbersImpl2().findMinFibonacciNumbers(i));
        }



        System.out.println(new FindMinFibonacciNumbersImpl1().findMinFibonacciNumbers(TEST_01));
    }
    static final int NOT_INIT = -1;

    /**
     * 从1-k，穷举出所有元素的最小数，返回 minFibonacciNumbers[k]，时间为o(n^2),超时
     * @param k
     * @return
     */
    @Override
    public int findMinFibonacciNumbers(int k) {
        if(k >= 10000){
            return -1;
        }
        int[] minFibonacciNumbers = new int[k > 2 ? (k + 1) : 3];
        initMinFibonacciNumbers(minFibonacciNumbers, k);
        for (int i = 1; i < minFibonacciNumbers.length; i++) {
            if(i % 1000 == 0){
                System.out.println(i);
                System.out.println(i >= TEST_01);
                if(i >= TEST_01){
                    break;
                }
            }
            if(minFibonacciNumbers[i] == NOT_INIT){
                int left = 1,right = i - 1;
                int min = minFibonacciNumbers[left] + minFibonacciNumbers[right];

                while(left <= right){
                    int currentNumbers = minFibonacciNumbers[left] + minFibonacciNumbers[right];
                    if(min > currentNumbers){
                        min = currentNumbers;
                    }
                    left++;
                    right--;
                    if(minFibonacciNumbers[right + 1] == 1){
                        break;
                    }
                }
                minFibonacciNumbers[i] = min;
            }
        }
        return minFibonacciNumbers[k];
    }

    /**
     * 初始化最小斐波那契和序列数组
     * @param minFibonacciNumbers
     * @param k
     */
    private void initMinFibonacciNumbers(int[] minFibonacciNumbers, int k){
        int fib1 = 1,fib2 = 1,fib3 = fib1 + fib2;
        for (int i = 0; i < minFibonacciNumbers.length; i++) {
            minFibonacciNumbers[i] = NOT_INIT;
        }
        minFibonacciNumbers[1] = 1;
        minFibonacciNumbers[2] = 1;
        while(fib3 <= k){
            minFibonacciNumbers[fib3] = 1;
            fib1 = fib2;
            fib2 = fib3;
            fib3 = fib1 + fib2;
        }
    }
}
/**
 *  设和为K的斐波那契数为 M = {S,I(K)} ，I(K)为所有和为K的最小斐波那契数集合的集合
 *  要证明每次取最大的斐波那契数的贪心策略是正确的，只需要证明M为一个拟阵
 *  1.证明遗传性
 *      设集合 B ∈ I(K)，即B是最少的和为K的斐波那契数的一个解，
 *      且 A ⊆ B， A 中元素为之和为 K'，则必有 A ∈ I(K')
 *      否则一定可以找到集合A'，|A'| < |A|，使得 A' U (B - A) = C， C ∈ I(K)
 *      因此 |C| < |B|, 得到B ∉ I(K)，与假设矛盾
 *  2.证明交换性
 *      设集合A中元素之和为M，集合B中元素之和为K，且有|A|<|B|,A ∈ I(M),B ∈ I(K)
 *      则 ∃x ∈ B - A,使得 {x} U A ∈ I(M + x)
 *      反例 {1，5，13} ∈ I(19), {1,8} ∈ I(9)
 *          {1,5,8} ∉ I(14) , {1,8,13} ∉ I(22)
 *      因此不具有拟阵性质
 */

class FindMinFibonacciNumbersImpl2 implements FindMinFibonacciNumbers{
    /**
     * 贪心法，每次找出不超过 k 的最大斐波那契数加入集合，继续求解子问题
     * @param k
     * @return
     */
    @Override
    public int findMinFibonacciNumbers(int k) {
        List<Integer> fibonacciSeries = new ArrayList<>();
        int fib1 = 1,fib2 = 1,fib3 = fib1 + fib2;
        fibonacciSeries.add(-1);
        fibonacciSeries.add(fib1);
        fibonacciSeries.add(fib2);
        while (fib3 <= k){
            fibonacciSeries.add(fib3);
            fib1 = fib2;
            fib2 = fib3;
            fib3 = fib2+fib1;
        }
        int iter = 0;
        for (int i = fibonacciSeries.size() ; i > 0; i--) {
            int curFibNumber = fibonacciSeries.get(i);
            if(curFibNumber <= k && k > 0){
                k -= curFibNumber;
                iter++;
            }
        }
        return iter;
    }
    /*
    private int findMaxFibonacci(List<Integer> fibonacciSeries, int k){
        int maxPos = 0;
        for (int i = 1; i < fibonacciSeries.size(); i++) {
            if(fibonacciSeries.get(i) <= k){
                maxPos = i;
            }else{
                break;
            }
        }
        return maxPos;
    }
   */
}